package dp.leetcode_322;

public class Recursion {
    /*
        从左往右依次尝试，选择价值为 coins[i] 的金额，剩余总金额 = amount - coins[i]
     */
    public int coinChange(int[] coins, int amount) {
        return getMinCoinsNumber(coins, amount);
    }

    public int getMinCoinsNumber(int[] coins, int amount) {
        // base - case
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        // 使用「正无穷」表示如果 1 种选择方案都不存在的情况
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int ways = getMinCoinsNumber(coins, amount - coins[i]);
            if (ways == -1) {
                continue;
            }
            // ways != -1，说明找到了一种方案，将方案数加 1，并更新最终结果
            res = Math.min(res, ways + 1);
        }
        // 如果最终 res 仍然是「正无穷」表示没有任何一种硬币组合能够拼成 amount 返回 -1
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
